#include <iostream>
#include <stack>
#include <unordered_map>

bool isValidBracketSequence(const std::string& sequence) {
    std::stack<char> bracketStack;
    std::unordered_map<char, char> bracketPairs = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'},
        {'<', '>'}
    };

    for (char bracket : sequence) {
        if (bracketPairs.find(bracket) != bracketPairs.end()) {
            // ��� ����������� ������, �������� �� � ����
            bracketStack.push(bracket);
        } else {
            // ��� ����������� ������
            if (bracketStack.empty() || bracket != bracketPairs[bracketStack.top()]) {
                // ���� ���� ���� ��� ������� ����������� ������ �� ������������� ����������� � �����
                return false;
            }
            bracketStack.pop();
        }
    }

    // ���������, ��� ���� ���� ����� ��������� ���� ������������������
    return bracketStack.empty();
}

int main() {
    std::string input;
    std::cout << "Enter the bracket sequence: ";
    std::cin >> input;

    if (isValidBracketSequence(input)) {
        std::cout << "True" << std::endl;
    } else {
        std::cout << "False" << std::endl;
    }

    return 0;
}

